package com.fan.kruskal;

import java.util.*;

/**
 * 克鲁斯卡尔算法
 *
 * @author 19252
 * @date 2020/8/7
 */
public class KruskalDemo {

    public static void main(String[] args) {
        KruskalGraph graph = new KruskalGraph(7);
        char[] vertexArray = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        graph.setVertexArray(vertexArray);
        /*// A
        graph.setEdge(0, 1, 12);
        graph.setEdge(0, 5, 16);
        graph.setEdge(0, 6, 14);
        // B
        graph.setEdge(1, 0, 12);
        graph.setEdge(1, 2, 10);
        graph.setEdge(1, 5, 7);
        // C
        graph.setEdge(2, 1, 10);
        graph.setEdge(2, 3, 3);
        graph.setEdge(2, 4, 5);
        graph.setEdge(2, 5, 6);
        // D
        graph.setEdge(3, 2, 3);
        graph.setEdge(3, 4, 4);
        // E
        graph.setEdge(4, 2, 5);
        graph.setEdge(4, 3, 4);
        graph.setEdge(4, 5, 2);
        graph.setEdge(4, 6, 8);
        // F
        graph.setEdge(5, 0, 16);
        graph.setEdge(5, 1, 7);
        graph.setEdge(5, 2, 6);
        graph.setEdge(5, 4, 2);
        graph.setEdge(5, 6, 9);
        // G
        graph.setEdge(6, 0, 14);
        graph.setEdge(6, 4, 8);
        graph.setEdge(6, 5, 9);*/

        // graph.showEdges();
        // graph.showGraph();

/*        graph.setEdge(0, 1, 5);
        graph.setEdge(0, 2, 7);
        graph.setEdge(0, 6, 2);
        graph.setEdge(1, 0, 5);
        graph.setEdge(1, 3, 9);
        graph.setEdge(1, 6, 3);
        graph.setEdge(2, 0, 7);
        graph.setEdge(2, 4, 8);
        graph.setEdge(3, 1, 9);
        graph.setEdge(3, 5, 4);
        graph.setEdge(4, 2, 8);
        graph.setEdge(4, 5, 5);
        graph.setEdge(4, 6, 4);
        graph.setEdge(5, 3, 4);
        graph.setEdge(5, 4, 5);
        graph.setEdge(5, 6, 6);
        graph.setEdge(6, 0, 2);
        graph.setEdge(6, 1, 3);
        graph.setEdge(6, 4, 4);
        graph.setEdge(6, 5, 6);*/
        System.out.println("最小生成树");
        ArrayList<Edge> minTree = KruskalMinTree.getMinTree(graph);
        for (Edge edge : minTree){
            System.out.println(edge);
        }
    }

}

/**
 * 最小生成树
 */
class KruskalMinTree {

    /**
     * 最小生成树
     */
    public static ArrayList<Edge> minTree = new ArrayList<>();

    /**
     * 保存各个还未合并的最下生成树顶点
     */
    public static ArrayList<HashSet<Integer>> vertexSet = new ArrayList<>();

    public static ArrayList<Edge> getMinTree(KruskalGraph graph) {
        // 在进行最小生成树的计算之前，先对 graph 中的保存边的集合进行排序
        Collections.sort(graph.getEdgeArrayList());
        ArrayList<Edge> edgeArrayList = graph.getEdgeArrayList();
        int size = graph.getEdgeArrayList().size();
        System.out.println(size);
        // 去掉重复的边（无向图）
        for (int i = 1; i <= size / 2; i++) {
            edgeArrayList.remove(i);
        }
        /*for (Edge edge : edgeArrayList) {
            System.out.println(edge);
        }*/
        // 开始生成最小生成树
        for (int i = 0; i < graph.getVertexNum() - 1; i++) {
            for (int j = 0; j < edgeArrayList.size(); j++) {
                Edge edge = edgeArrayList.get(j);
                if (joinToMinTree(edge)) {
                    minTree.add(edge);
                    // 移除已经遍历的边
                    edgeArrayList.remove(j);
                    break;
                }
            }
        }
        return minTree;
    }

    /**
     * 判断选中的边是否符合最小生成树的要求
     *
     * @param edge 边
     * @return true 符合最小生成树的要求，false 不符合
     */
    private static boolean joinToMinTree(Edge edge) {
        // 开辟新的 new HashSet<>() 防止数据存储混乱
        HashSet<Integer> temp = new HashSet<>();
        // 临时变量
        boolean containsFlag1;
        boolean containsFlag2;
        int hashSetIndex = -1;
        int hashSetIndex2 = -1;
        if (minTree.size() != 0) {
            // 如果两个顶点早就加入minTree，那就判断会不会形成回路
            for (int i = 0; i < vertexSet.size(); i++) {
                containsFlag1 = vertexSet.get(i).contains(edge.getStartVertex());
                containsFlag2 = vertexSet.get(i).contains(edge.getEndVertex());
                // 有一条子树完全包含这两点，所以一定会形成回路，不能添加
                if (containsFlag1 && containsFlag2) {
                   return false;
                }
                // 记录只包含一个顶点的子树
                if (!containsFlag2 && containsFlag1) {
                    hashSetIndex = i;
                }
                // 同上
                if (!containsFlag1 && containsFlag2) {
                    hashSetIndex2 = i;
                }
            }
            // 这一次加入的边连接不同的两条子树，比较大小，将小的那条加入大的那条
            if (hashSetIndex > -1 && hashSetIndex2 > -1) {
                // 比较树的大小
                if (vertexSet.get(hashSetIndex).size() > vertexSet.get(hashSetIndex2).size()) {
                    for (Integer vertex : vertexSet.get(hashSetIndex2)) {
                        vertexSet.get(hashSetIndex).add(vertex);
                    }
                    // 两条树合并之后，将短的那条移除
                    vertexSet.remove(hashSetIndex2);
                } else {
                    for (Integer vertex : vertexSet.get(hashSetIndex)) {
                        vertexSet.get(hashSetIndex2).add(vertex);
                    }
                    // 两条树合并之后，将短的那条移除
                    vertexSet.remove(hashSetIndex);
                }

            } else {

                // 新加入的边有一个节点被包含在 minTree 的一条子树中，将没有被包含的点加入子树
                if (hashSetIndex > -1) {
                    vertexSet.get(hashSetIndex).add(edge.getStartVertex());
                    vertexSet.get(hashSetIndex).add(edge.getEndVertex());
                }else if (hashSetIndex2 > -1) {
                    vertexSet.get(hashSetIndex2).add(edge.getStartVertex());
                    vertexSet.get(hashSetIndex2).add(edge.getEndVertex());
                }else {
                    // 没有包含这一条边的最小生成树，就新创建一个
                    temp.add(edge.getStartVertex());
                    temp.add(edge.getEndVertex());
                    vertexSet.add(temp);
                }
            }

        } else {
            // 没有包含这一条边的最小生成树，就新创建一个
            temp.add(edge.getStartVertex());
            temp.add(edge.getEndVertex());
            vertexSet.add(temp);
        }
        return true;
    }
}

/**
 * 图
 */
class KruskalGraph {

    /**
     * 图中顶点的个数
     */
    private int vertexNum;

    /**
     * 图中边的条数
     */
    private int edgeNums;

    /**
     * 保存图中所有边的集合
     */
    private ArrayList<Edge> edgeArrayList = new ArrayList<>();

    /**
     * 图中的顶点
     */
    private char[] vertexArray;

    /**
     * 邻接矩阵
     */
    private int[][] matrix;

    /**
     * 标记图中对应下标的顶点是否被访问过
     */
    private boolean[] isVisited;

    /**
     * unreachable 不可达
     * unreachable 定义为一个非常大的值
     * 表示两点之间不连通
     */
    private int unreachable = Integer.MAX_VALUE;

    /**
     * 初始化图的基本信息
     * @param vertexNum 图中顶点的个数
     */
    public KruskalGraph(int vertexNum) {
        this.vertexNum = vertexNum;
        matrix = new int[vertexNum][vertexNum];
        isVisited = new boolean[vertexNum];
        // 默认图中所有的点不可达
        for (int i = 0; i < vertexNum; i++) {
            Arrays.fill(matrix[i], unreachable);
        }
    }

    /**
     * 为图填充数据，设置图中两点的距离
     *
     * @param vertex1 顶点
     * @param vertex2 顶点
     * @param weight  两个连接的顶点间的权值（在这里就是两点间的距离）
     */
    public void setEdge(int vertex1, int vertex2, int weight) {
        matrix[vertex1][vertex2] = weight;
        edgeArrayList.add(new Edge(vertex1, vertex2, weight));
        edgeNums++;
    }

    /**
     * 对边按权值从小到大排序展示
     */
    public void showEdges() {
        int startVertex;
        int endVertex;
        int weight;
        Collections.sort(edgeArrayList);
        for (int i = 0; i < edgeNums; i++) {
            startVertex = edgeArrayList.get(i).getStartVertex();
            endVertex = edgeArrayList.get(i).getEndVertex();
            weight = edgeArrayList.get(i).getWeight();
            System.out.println(vertexArray[startVertex] + "<->" + vertexArray[endVertex] + "::" + weight);
        }
    }

    /**
     * 展示图
     */
    public void showGraph() {
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                System.out.printf("%-15d", matrix[i][j]);
            }
            System.out.println();
        }
    }

    public int getVertexNum() {
        return vertexNum;
    }

    public void setVertexNum(int vertexNum) {
        this.vertexNum = vertexNum;
    }

    public char[] getVertexArray() {
        return vertexArray;
    }

    public void setVertexArray(char[] vertexArray) {
        this.vertexArray = vertexArray;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    public int getUnreachable() {
        return unreachable;
    }

    public void setUnreachable(int unreachable) {
        this.unreachable = unreachable;
    }

    public boolean[] getIsVisited() {
        return isVisited;
    }

    public void setIsVisited(boolean[] isVisited) {
        this.isVisited = isVisited;
    }

    public int getEdgeNums() {
        return edgeNums;
    }

    public void setEdgeNums(int edgeNums) {
        this.edgeNums = edgeNums;
    }

    public ArrayList<Edge> getEdgeArrayList() {
        return edgeArrayList;
    }

    public void setEdgeArrayList(ArrayList<Edge> edgeArrayList) {
        this.edgeArrayList = edgeArrayList;
    }
}

/**
 * 边
 */
class Edge implements Comparable<Edge> {
    private int startVertex;
    private int endVertex;
    private int weight;

    public Edge(int startVertex, int endVertex, int weight) {
        this.startVertex = startVertex;
        this.endVertex = endVertex;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        int result = this.weight - o.weight;
        if (result == 0) {
            result = (this.startVertex - o.startVertex) + (this.endVertex - o.endVertex);
        }
        return result;
    }

    public int getStartVertex() {
        return startVertex;
    }

    public void setStartVertex(int startVertex) {
        this.startVertex = startVertex;
    }

    public int getEndVertex() {
        return endVertex;
    }

    public void setEndVertex(int endVertex) {
        this.endVertex = endVertex;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "startVertex=" + startVertex +
                ", endVertex=" + endVertex +
                ", weight=" + weight +
                '}';
    }
}

